W11. Недетерминированные PDA и TM, алгоритм Клини и порождающие грамматики

Автор

Manuel Mazzara

Дата публикации

2 апреля 2026 г.

1. Краткое содержание

1.1 Недетерминированные автоматы с магазином

1.1.1 Напоминание: детерминированный PDA

Детерминированный автомат с магазином (DPDA) — это 7-кортеж \(\langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\), где:

\(Q\) — конечное множество состояний;
\(I\) — конечный входной алфавит;
\(\Gamma\) — конечный алфавит магазина;
\(\delta : Q \times (I \cup \{\epsilon\}) \times \Gamma \rightarrow Q \times \Gamma^*\) — (частичная) функция переходов: для каждого состояния, опционального входного символа и символа на вершине стека определено не более одной следующей конфигурации;
\(q_0 \in Q\) — начальное состояние;
\(Z_0 \in \Gamma\) — начальный символ магазина;
\(F \subseteq Q\) — множество принимающих состояний.

Ключевое ограничение детерминизма: функция переходов не более однозначна: для любой тройки \((q, i, A)\) существует не более одного возможного хода. Дополнительно действует правило отсутствия конфликта для \(\epsilon\)-ходов: если \(\delta(q, \epsilon, A)\) определена, то \(\delta(q, i, A)\) должна быть неопределённой для всех \(i \in I\).

1.1.2 Недетерминированный PDA: формальное определение

Недетерминированный автомат с магазином (NPDA) задаётся тем же 7-кортежем, но функция переходов может возвращать множество возможных следующих конфигураций:

\[\delta : Q \times (I \cup \{\epsilon\}) \times \Gamma \rightarrow \mathbb{P}_F(Q \times \Gamma^*)\]

где \(\mathbb{P}_F\) обозначает множество всех конечных подмножеств \(Q \times \Gamma^*\). У автомата из любой конфигурации может быть ноль, один или несколько возможных переходов. Строка \(x\) принимается, если по крайней мере один возможный путь вычисления приводит к принимающему состоянию — это стандартное экзистенциальное условие принятия.

Главное отличие от DPDA: ограничение «без конфликта» для \(\epsilon\)-ходов снято: из состояния \(q\) при вершине стека \(A\) и множествах \(\delta(q, \epsilon, A)\) и \(\delta(q, i, A)\) оба могут быть непустыми, что даёт подлинный недетерминизм.

1.1.3 NPDA и DPDA: выразительная сила

Недетерминизм для PDA увеличивает выразительную силу — в отличие от конечных автоматов, где NFSA и DFSA распознают одни и те же языки.

Канонический пример — \(L = \{a^n b^n \mid n \geq 1\} \cup \{a^n b^{2n} \mid n \geq 1\}\). Ни один DPDA не распознаёт этот язык: после чтения всех \(a\) автомату пришлось бы одновременно подготовить два разных содержимых стека (один \(a\) на каждый \(b\) или один \(a\) на каждые два \(b\)). NPDA справляется, угадывая недетерминированно, к какому из двух языков относится вход: он кладёт \(a\) в стек (парами или по одному) и затем снимает при чтении \(b\).

Отсюда базовая иерархия:

\[\text{REG} \subsetneq \text{DCFL} \subsetneq \text{CFL}\]

где CFL (контекстно-свободные языки) — в точности класс языков, распознаваемых NPDA. DCFL (детерминированные контекстно-свободные языки) — собственное подмножество CFL.

NPDA для {aⁿbⁿ | n ≥ 1} ∪ {aⁿb²ⁿ | n ≥ 1}: недетерминированное ветвление при чтении первого b

1.2 Свойства замкнутости NPDA

Класс языков, распознаваемых NPDA (контекстно-свободные языки, CFL), имеет принципиально другой профиль замкнутости, чем регулярные языки и детерминированные CFL.

1.2.1 Объединение: NPDA замкнут

Даны два NPDA: NPDA\(_1\) распознаёт \(L_1\), NPDA\(_2\) — \(L_2\). Строим NPDA для \(L_1 \cup L_2\) так: вводим новое начальное состояние \(q_0\) и два \(\epsilon\)-перехода — один в начальное состояние NPDA\(_1\), другой в начальное NPDA\(_2\). На любом входе автомат недетерминированно входит в одно из двух исходных автоматов.

\[L_1, L_2 \in \textbf{CFL} \implies L_1 \cup L_2 \in \textbf{CFL}\]

Класс CFL замкнут относительно \(\cup\).

1.2.2 Пересечение: NPDA не замкнут

Рассмотрим два языка над \(\{a, b, c\}\):

\[L_1 = \{a^n b^n c^m \mid n, m > 0\} \in \textbf{DPDA} \subseteq \textbf{CFL}\] \[L_2 = \{a^m b^n c^n \mid n, m > 0\} \in \textbf{DPDA} \subseteq \textbf{CFL}\]

Их пересечение:

\[L_1 \cap L_2 = \{a^n b^n c^n \mid n > 0\}\]

Этот язык не контекстно-свободен (нужна проверка с двумя «счётчиками», которую стековая машина выполнить не может). Следовательно:

Класс CFL не замкнут относительно \(\cap\).

Причина в том, что стек — одна линейная память. Использовав её, чтобы сопоставить \(a\) с \(b\), нельзя одновременно сопоставить \(b\) с \(c\).

1.2.3 Дополнение: NPDA не замкнут

Это сразу следует из замкнутости по объединению и незамкнутости по пересечению через законы де Моргана:

\[L_1 \cap L_2 = (L_1^c \cup L_2^c)^c\]

Если бы CFL были замкнуты относительно дополнения, то вместе с замкнутостью по объединению они были бы замкнуты и по пересечению — противоречие. Значит:

Класс CFL не замкнут относительно дополнения \((\,\cdot\,)^c\).

Замечание: DPDA замкнут относительно дополнения (после полного автомата можно поменять местами принимающие и непринимающие состояния), а NPDA — нет, потому что при экзистенциальном принятии замена состояний некорректна. Если вход \(w\) обрабатывается по двум веткам — одна принимает, другая отвергает, — то \(w\) принимается. После обмена ветка A отвергает, ветка B принимает, и \(w\) по-прежнему принимается, хотя в корректном дополнении должен был бы отвергаться.

1.2.4 Разность: NPDA не замкнут

Так как \(L^c = I^* \setminus L\), замкнутость по разности множеств влекла бы замкнутость по дополнению. CFL не замкнуты по дополнению, поэтому:

Класс CFL не замкнут относительно \(\setminus\).

1.2.5 Таблица замкнутости

	\(\cup\)	\(\cap\)	\(\setminus\)	дополнение
Регулярные (FSA)	да	да	да	да
DCFL (DPDA)	нет	нет	нет	да
CFL (NPDA)	да	нет	нет	нет

1.2.6 Лемма о накачке для контекстно-свободых языков (лемма Бар-Хиллеля)

Как лемма о накачке для регулярных языков позволяет доказать нерегулярность, лемма Бар-Хиллеля даёт необходимое условие контекстно-свободности. Если \(L\) распознаётся некоторым NPDA, то существует константа \(m \geq 1\) такая, что каждая строка \(w \in L\) с \(|w| \geq m\) раскладывается как \(w = x_1 x_2 x_3 x_4 x_5\), причём:

\(|x_2 x_4| > 0\) — хотя бы одна из \(x_2, x_4\) непуста;
\(|x_2 x_3 x_4| \leq m\) — «накачиваемый» фрагмент не слишком длинный;
\(x_1 x_2^i x_3 x_4^i x_5 \in L\) для любого \(i \geq 0\).

Применение. \(L = \{a^n b^n c^n \mid n > 0\}\) не является CFL. Любая попытка накачки строки вида \(a^m b^m c^m\) вынудит \(x_2\) и \(x_4\) пересечь не более двух из трёх типов символов, поэтому накачка меняет кратности не более чем у двух букв и нарушает равенство \(a^n = b^n = c^n\).

1.3 Недетерминированная машина Тьюринга

1.3.1 Формальное определение

Недетерминированная машина Тьюринга (NTM) получается из детерминированной MT изменением только функции переходов. NTM по-прежнему 7-кортеж \(\langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\), где \(Q, I, \Gamma, q_0, Z_0, F\) определены так же, как у DTM. Функция переходов становится:

\[\delta : (Q - F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\})^k \rightarrow \mathbb{P}\!\left(Q \times (\Gamma \cup \{\_\})^k \times \{R, L, S\}^{k+1}\right)\]

Вместо одной следующей конфигурации \(\delta\) возвращает множество возможных следующих конфигураций (состояние, записываемые символы ленты, направления головок). Для варианта трансдьюсера отображение выхода \(\eta\) аналогично обобщается до множества.

Условие принятия. Строка \(x\) принимается NTM тогда и только тогда, когда по крайней мере один из возможных путей вычисления из начальной конфигурации на входе \(x\) достигает принимающего состояния. Снова экзистенциальный недетерминизм: достаточно одного успешного пути.

1.3.2 Дерево вычислений

Вычисление детерминированной MT на фиксированном входе — одна последовательность конфигураций, «линия». Вычисление NTM — дерево: на каждом шаге машина может разветвиться на несколько веток, по одной на каждый элемент множества \(\delta\). Дерево может экспоненциально разрастаться с глубиной.

Условие принятия гласит: вход принят, если какой-либо путь в дереве вычислений достигает принимающего (финального) состояния \(F\). Пути, останавливающиеся в непринимающем состоянии, — отклонение на этой ветке; бесконечные пути — незавершающиеся ветки.

Дерево вычислений NTM: ветвление; если хотя бы один путь достигает принимающей конфигурации (синий квадрат), вход принимается

1.3.3 Моделирование NTM с помощью DTM: поиск в ширину

Может ли детерминированная MT моделировать недетерминированную? Ответ — да, с помощью поиска в ширину (BFS) по дереву вычислений.

Почему не DFS? Обход в глубину следует одной ветке до конца. Если эта ветка бесконечна (незавершающееся вычисление), DFS не возвращается и не исследует другие ветки, хотя принимающие конфигурации могут существовать. Это родственно проблеме остановки: заранее неизвестно, бесконечна ветка или просто длинна.

Моделирование BFS. DTM, моделирующая NTM, посещает узлы дерева вычислений по уровням: сначала все конфигурации, достижимые за 0 шагов, затем за 1 шаг, затем за 2 и т.д. Если принимающая конфигурация существует на конечной глубине, BFS достигнет её за конечное время.

Моделирование BFS использует многоленточную DTM:

Одна лента хранит входную строку.
Одна лента поддерживает очередь конфигураций для обхода (сериализованную в строки).
Одна лента выполняет моделирование каждого шага NTM.

Следствие. Каждый язык, распознаваемый NTM, распознаётся и некоторой DTM. Недетерминизм не добавляет выразительной силы машинам Тьюринга, только (потенциально экспоненциальное) ускорение алгоритма.

1.3.4 Итог: DTM и NTM

DFSA и NFSA: одинаковая выразительная сила (регулярные языки).
DPDA и NPDA: разная выразительная сила — NPDA строго сильнее.
DTM и NTM: одинаковая выразительная сила (рекурсивно перечислимые языки).

Семейство PDA — единственный случай, когда детерминизм и недетерминизм дают разные классы языков.

1.4 От DFSA к регулярному выражению: алгоритм Клини

1.4.1 Наглядная основа

Каждый конечный автомат можно преобразовать в эквивалентное регулярное выражение. Преобразование опирается на три алгебраических наблюдения:

Объединение: два параллельных ребра \(q \xrightarrow{x} p\) и \(q \xrightarrow{y} p\) можно слить в одно \(q \xrightarrow{x \mid y} p\).
Конкатенация: путь \(q \xrightarrow{x} t \xrightarrow{y} p\) через промежуточное \(t\) сворачивается в одно ребро \(q \xrightarrow{x \cdot y} p\), исключая \(t\).
Звезда Клини: петля \(q \xrightarrow{x} q\) означает повторение \(x\) произвольное число раз, то есть выражение \(x^*\).

Систематически исключая промежуточные состояния этими тремя правилами, весь автомат сводится к регулярным выражениям на прямых рёбрах от начального состояния к каждому принимающему.

1.4.2 Формальный алгоритм

Пусть \(M = \langle Q, \Sigma, \delta, q_0, F \rangle\) — DFSA с \(Q = \{q_0, q_1, \ldots, q_n\}\).

База (\(k = -1\)). Определим \(R_{ij}^{-1}\) как регулярное выражение для всех прямых переходов из \(q_i\) в \(q_j\):

\[R_{ij}^{-1} = \begin{cases} a_1 \mid \cdots \mid a_m \mid \epsilon, & i = j \text{ and } \delta(q_i, a_t) = q_j \text{ for some } a_t \\ a_1 \mid \cdots \mid a_m, & i \neq j \text{ and } \delta(q_i, a_t) = q_j \text{ for some } a_t \\ \emptyset, & \text{no direct transition from } q_i \text{ to } q_j \end{cases}\]

\(\epsilon\) на диагонали (\(i = j\)) соответствует возможности остаться в \(q_i\), не читая вход.

Индукция (\(k = 0, 1, \ldots, n\)). На каждой итерации «разрешаются» пути, проходящие через \(q_k\):

\[R_{ij}^k = R_{ik}^{k-1} \left(R_{kk}^{k-1}\right)^* R_{kj}^{k-1} \;\mid\; R_{ij}^{k-1}\]

Смысл: \(R_{ij}^k\) описывает все пути из \(q_i\) в \(q_j\), где промежуточными могут быть только \(q_0, \ldots, q_k\). Первое слагаемое добавляет пути: из \(q_i\) в \(q_k\), любое число обходов вокруг \(q_k\), затем в \(q_j\).

Ответ. Если \(F = \{q_{i_1}, \ldots, q_{i_f}\}\) — множество принимающих состояний, регулярное выражение для \(L(M)\):

\[R_{0,i_1}^n \mid R_{0,i_2}^n \mid \cdots \mid R_{0,i_f}^n\]

Семантика \(R_{ij}^k\). Выражение \(R_{ij}^k\) задаёт все строки, переводящие \(M\) из \(q_i\) в \(q_j\) без прохода через состояния с индексом больше \(k\) в качестве промежуточных. При \(k = n\) ограничений нет, и \(R_{0j}^n\) — все строки из начального состояния в \(q_j\).

1.5 \(\epsilon\)-ходы и автоматы с магазином

1.5.1 FSA с \(\epsilon\)-переходами

В курсе PDA уже определены с \(\epsilon\)-ходами (спонтанные переходы без чтения входа). Для FSA \(\epsilon\)-переходы до сих пор не рассматривались. Недетерминированный FSA с \(\epsilon\)-переходами (NFSA-\(\epsilon\)) допускает \(\delta(q, \epsilon) \neq \emptyset\). При этом:

\[\text{NFSA-}\epsilon \equiv \text{NFSA} \equiv \text{FSA}\]

Все три модели распознают в точности регулярные языки. \(\epsilon\)-переходы не добавляют мощности конечным автоматам.

1.5.2 Чувствительность PDA к вариантам модели

В отличие от FSA, PDA сильно чувствительны к мелким изменениям определения. Следующие изменения влияют на класс распознаваемых языков:

Принятие по финальному состоянию против принятия по пустому стеку — для NPDA эквивалентны, для DPDA не всегда.
Число стеков — PDA с двумя стеками уже эквивалентен MT.
Детерминизм и недетерминизм — разные классы языков (DCFL \(\subsetneq\) CFL).
С \(\epsilon\)-ходами и без — у DPDA удаление \(\epsilon\)-ходов снижает мощность.

Эта чувствительность делает семейство PDA богатым объектом для границ между моделями вычислений.

1.5.3 Детерминированные PDA в реальном времени

Realtime DPDA — это DPDA без \(\epsilon\)-ходов: каждый переход потребляет ровно один входной символ. Автомат обрабатывает вход в реальном времени — без внутренней работы без чтения входа.

Realtime DPDA строго слабее DPDA с \(\epsilon\)-ходами:

\[\text{REG} \subsetneq \text{RTDCFL} \subsetneq \text{DCFL} \subsetneq \text{CFL}\]

Пример. Язык \(L = \{a^n b^p c\, a^n \mid p, n > 0\} \cup \{a^n b^p d\, b^p \mid p, n > 0\}\) требует DPDA, но не распознаётся ни одним realtime DPDA. На ветке с \(c\) после чтения \(c\) нужно снять со стека все \(b\), чтобы добраться до подсчёта \(a\) ниже, но при этом нечего читать со входа — без \(\epsilon\)-ходов не обойтись.

1.5.4 Дополнение к NPDA

Для детерминированных машин, чьё вычисление всегда завершается, дополнение строится просто: полный автомат и обмен принимающих и непринимающих состояний. Так для DPDA.

Для NPDA это ломается из-за экзистенциального принятия. Рассмотрим недетерминированное вычисление \(w\) по двум веткам:

Ветка A: принимает.
Ветка B: отвергает.

Из-за экзистенциального недетерминизма \(w\) принимается исходным NPDA. После обмена состояний ветка A отвергает, ветка B принимает — \(w\) всё ещё принимается «переставленным» автоматом, хотя в корректном дополнении должен отвергаться. Подход с обменом состояний для недетерминизма не работает.

1.5.5 Языки, распознаваемые NPDA

Языки, распознаваемые NPDA, — в точности контекстно-свободные языки (CFL). CFL строго между детерминированными CFL и рекурсивно перечислимыми.

Иерархия языков: регулярные ⊊ детерминированные CFL ⊊ контекстно-свободные ⊊ рекурсивно перечислимые

1.6 Порождающие грамматики

1.6.1 Операционные и порождающие модели

До этого в курсе изучались операционные модели (автоматы): машины получают вход и решают, принять ли его. Есть двойственное семейство порождающих моделей (грамматики): наборы правил строят строки языка.

Автоматы (операционные): отвечают на вопрос «находится ли \(x\) в языке?»
Грамматики (порождающие): отвечают на вопрос «как можно построить строки языка?»

Обе точки зрения важны; иерархия Хомского показывает соответствие: каждому классу автоматов соответствует класс грамматик.

В разборе грамматики задают синтаксис языков программирования, а автоматы обрабатывают исходный код, проверяя синтаксис. Грамматики часто недетерминированы, но практические генераторы парсеров используют тщательно спроектированные детерминированные грамматики с предпросмотром.

1.6.2 Формальное определение грамматики

Формальная грамматика — это 4-кортеж \(G = \langle V_N, V_T, P, S \rangle\), где:

\(V_N\) — конечный алфавит нетерминалов (переменные; по соглашению — заглавные буквы);
\(V_T\) — конечный алфавит терминалов (символы порождаемого языка; по соглашению — строчные);
\(V = V_N \cup V_T\) — объединённый словарь;
\(S \in V_N\) — аксиома (начальный символ);
\(P \subseteq V^* \cdot V_N \cdot V^* \times V^*\) — конечное множество продукций (правил переписывания), записываемых \(\alpha \rightarrow \beta\).

Продукция \(\alpha \rightarrow \beta\) состоит из:

Левой части \(\alpha \in V^* \cdot V_N \cdot V^*\): строка, содержащая хотя бы один нетерминал;
Правой части \(\beta \in V^*\): произвольная (возможно пустая) строка из терминалов и нетерминалов.

Грамматика порождает строки, многократно заменяя подстроки, совпадающие с левой частью продукции, на соответствующую правую часть.

1.6.3 Непосредственный вывод и порождённый язык

Непосредственный вывод. \(\alpha \Rightarrow \beta\) (читается: «\(\beta\) получается из \(\alpha\) одним шагом вывода») тогда и только тогда, когда:

\[\alpha = \alpha_1 \alpha_2 \alpha_3, \quad \beta = \alpha_1 \beta_2 \alpha_3, \quad \text{and} \quad \alpha_2 \rightarrow \beta_2 \in P\]

То есть \(\alpha_2\) переписывается в \(\beta_2\) в контексте \(\langle \alpha_1, \alpha_3 \rangle\). Слово «контекст» осознанно: контекстно-зависимые грамматики как раз определяются нетривиальным контекстом в левой части.

Порождённый язык. Для \(G = \langle V_N, V_T, P, S \rangle\) язык, порождённый \(G\):

\[L(G) = \{x \mid x \in V_T^* \text{ and } S \Rightarrow^+ x\}\]

То есть \(L(G)\) — все строки над алфавитом терминалов, выводимые из аксиомы \(S\) за один или более шаг с помощью продукций \(P\) в любом порядке.

1.6.4 Иерархия Хомского грамматик

Иерархия Хомского классифицирует грамматики по форме правил, задавая вложенное семейство классов языков:

Тип Хомского	Грамматика	Класс языков	Минимальный автомат
Тип 0	Неограниченные	Рекурсивно перечислимые	Машина Тьюринга
Тип 1	Контекстно-зависимые	Контекстно-зависимые	Линейно ограниченный автомат
Тип 2	Контекстно-свободные	Контекстно-свободные	NPDA
Тип 3	Регулярные	Регулярные	FSA

Каждый уровень — строгое подмножество уровня выше. Контекстно-свободные грамматики (тип 2) особенно важны для проектирования языков программирования: всякая КС-грамматика разбирается NPDA, а аккуратно спроектированные детерминированные грамматики эффективно разбираются стандартными генераторами (LL, LR).

2. Определения

DPDA (детерминированный автомат с магазином): 7-кортеж \(\langle Q, I, \Gamma, \delta, q_0, Z_0, F \rangle\) с \(\delta : Q \times (I \cup \{\epsilon\}) \times \Gamma \rightarrow Q \times \Gamma^*\); не более одного хода из каждой конфигурации и отсутствие \(\epsilon\)-конфликта.
NPDA (недетерминированный автомат с магазином): та же структура, что у DPDA, но \(\delta : Q \times (I \cup \{\epsilon\}) \times \Gamma \rightarrow \mathbb{P}_F(Q \times \Gamma^*)\); из конфигурации допускается несколько переходов.
Контекстно-свободный язык (CFL): язык, распознаваемый некоторым NPDA; эквивалентно — порождённый контекстно-свободной грамматикой (тип 2 по Хомскому).
Детерминированный контекстно-свободный язык (DCFL): язык, распознаваемый некоторым DPDA; собственное подмножество CFL.
Лемма Бар-Хиллеля (о накачке для CFL): если \(L\) — CFL, существует \(m \geq 1\) такое, что любое \(w \in L\) с \(|w| \geq m\) раскладывается \(w = x_1 x_2 x_3 x_4 x_5\), где \(|x_2 x_4| > 0\), \(|x_2 x_3 x_4| \leq m\) и \(x_1 x_2^i x_3 x_4^i x_5 \in L\) для всех \(i \geq 0\).
NTM (недетерминированная машина Тьюринга): MT, у которой \(\delta\) возвращает множество конфигураций; принятие, если какой-либо путь вычисления достигает \(F\).
Дерево вычислений: ветвящееся дерево всех достижимых конфигураций NTM из начальной; принятие, если в дереве есть принимающая конфигурация.
Экзистенциальный недетерминизм: критерий принятия — существует хотя бы один принимающий путь вычисления (стандартно для NFSA, NPDA, NTM).
Моделирование BFS: приём DTM для моделирования NTM обходом дерева вычислений по уровням, гарантирующий нахождение любой принимающей конфигурации на конечной глубине.
Алгоритм Клини: процедура преобразования DFSA \(M\) с \(n+1\) состоянием в эквивалентное регулярное выражение через вычисление \(R_{ij}^k\) для \(k = -1, 0, \ldots, n\), где \(R_{ij}^k\) — все строки, переводящие \(M\) из \(q_i\) в \(q_j\) через промежуточные состояния с индексом не больше \(k\).
\(R_{ij}^{-1}\): базовые выражения алгоритма Клини; только прямые (одношаговые) переходы между \(q_i\) и \(q_j\) (плюс \(\epsilon\) на диагонали).
Realtime DPDA: DPDA без \(\epsilon\)-ходов; каждый переход читает ровно один входной символ; строго слабее DPDA с \(\epsilon\)-ходами.
Формальная грамматика: 4-кортеж \(\langle V_N, V_T, P, S \rangle\) с нетерминалами, терминалами, продукциями и начальным символом; порождает язык переписыванием.
Продукция: правило \(\alpha \rightarrow \beta\), где \(\alpha\) содержит хотя бы один нетерминал, а \(\beta\) — произвольная строка из терминалов и нетерминалов.
Аксиома (начальный символ): нетерминал \(S \in V_N\), с которого начинаются все выводы.
Непосредственный вывод (\(\Rightarrow\)): \(\alpha \Rightarrow \beta\), если \(\beta\) получается из \(\alpha\) применением одной продукции в некотором контексте.
Язык, порождённый \(G\): \(L(G) = \{x \in V_T^* \mid S \Rightarrow^+ x\}\) — все терминальные цепочки, выводимые из \(S\) за один или более шаг.
Иерархия Хомского: четырёхуровневая классификация грамматик (типы 0–3), соответствующая MT, LBA, NPDA и FSA.

3. Формулы

Функция переходов NPDA: \(\delta : Q \times (I \cup \{\epsilon\}) \times \Gamma \rightarrow \mathbb{P}_F(Q \times \Gamma^*)\)
Функция переходов NTM (\(k\) лент): \(\delta : (Q - F) \times (I \cup \{\_\}) \times (\Gamma \cup \{\_\})^k \rightarrow \mathbb{P}(Q \times (\Gamma \cup \{\_\})^k \times \{R, L, S\}^{k+1})\)
Принятие NTM: \(x\) принят \(\iff\) \(\exists\) путь вычисления в дереве \(M\) на \(x\), достигающий состояния из \(F\)
База Клини: \(R_{ij}^{-1} = \begin{cases} a_1 \mid \cdots \mid a_m \mid \epsilon & i = j \\ a_1 \mid \cdots \mid a_m & i \neq j \\ \emptyset & \text{no direct transition} \end{cases}\)
Шаг индукции Клини: \(R_{ij}^k = R_{ik}^{k-1}(R_{kk}^{k-1})^* R_{kj}^{k-1} \mid R_{ij}^{k-1}\)
Итог Клини: \(R_{0,i_1}^n \mid \cdots \mid R_{0,i_f}^n\), где \(F = \{q_{i_1}, \ldots, q_{i_f}\}\)
Язык грамматики: \(L(G) = \{x \in V_T^* \mid S \Rightarrow^+ x\}\)
Область продукций: \(P \subseteq V^* \cdot V_N \cdot V^* \times V^*\)
Непосредственный вывод: \(\alpha \Rightarrow \beta \iff \exists\, \alpha_1, \alpha_2, \alpha_3, \beta_2 : \alpha = \alpha_1\alpha_2\alpha_3,\; \beta = \alpha_1\beta_2\alpha_3,\; \alpha_2 \rightarrow \beta_2 \in P\)

4. Примеры

4.1. Построение NPDA для трёх языков (Лаба 10, Задание 1)

Постройте NPDA, распознающие следующие языки:

\(L_1 = \{ww^R \mid w \in \{a, b\}^+\}\), где \(w^R\) — разворот \(w\).
\(L_2 = \{a^n b^n \mid n \geq 1\} \cup \{a^n b^{2n} \mid n \geq 1\}\).
\(L_3 = \{a^i b^j c^k d^l \mid (i = k \text{ or } j = l),\; i \geq 1,\; j \geq 1\}\).

Показать решение

(a) \(L_1 = \{ww^R \mid w \in \{a, b\}^+\}\) — палиндромы чётной длины.

Идея: NPDA недетерминированно угадывает середину строки. В первой половине каждый символ кладётся на стек; во второй — снимается и сопоставляется. Так как \(w \in \{a,b\}^+\), обе половины непусты.

Состояния: \(q_0\) (фаза заталкивания), \(q_1\) (фаза снятия), \(q_2\) (принимающее).
Фаза заталкивания (\(q_0\)):
- \(a, Z_0 / AZ_0\) и \(a, A / AA\) и \(a, B / AB\) — для каждого \(a\) кладётся \(A\).
- \(b, Z_0 / BZ_0\) и \(b, A / BA\) и \(b, B / BB\) — для каждого \(b\) кладётся \(B\).
- Недетерминированные \(\epsilon\)-переходы в \(q_1\): \(\epsilon, Z_0/Z_0\), \(\epsilon, A/A\), \(\epsilon, B/B\) — угадывание середины (спонтанный ход).
Фаза снятия (\(q_1\)):
- \(a, A/\epsilon\) — сопоставить \(a\) с \(A\) на стеке.
- \(b, B/\epsilon\) — сопоставить \(b\) с \(B\) на стеке.
Принятие (\(q_1 \to q_2\)): \(\epsilon, Z_0/Z_0\) — принять, когда стек снова \(Z_0\) (все символы согласованы).

Корректность: \(\epsilon\)-переходы позволяют угадать середину в любой позиции; на верной ветке стек опустошается ровно при исчерпании \(w^R\).

(b) \(L_2 = \{a^n b^n \mid n \geq 1\} \cup \{a^n b^{2n} \mid n \geq 1\}\).

Используем построение объединения: в начале недетерминированно выбираем одну из двух веток.

Общее начало \(q_0\): на каждый прочитанный \(a\) кладутся два символа \(A\) (петли: \(a, Z_0/AAZ_0\); \(a, A/AAA\)).
Ветка для \(a^n b^{2n}\) (переход \(q_0 \xrightarrow{b, A/\epsilon} q_1\)): снимается один \(A\) на каждый \(b\); принятие при обнажении \(Z_0\).
- \(q_1\): петля \(b, A/\epsilon\); переход \(q_1 \xrightarrow{\epsilon, Z_0/Z_0} q_{\text{acc}}\).
Ветка для \(a^n b^n\) (переход \(q_0 \xrightarrow{b, A/\epsilon} q_3\), затем \(q_3 \xrightarrow{b, A/\epsilon} q_4 \xrightarrow{\epsilon, A/\epsilon} q_3\)): снимается один \(A\) на каждые два \(b\); принятие при обнажении \(Z_0\).
- \(q_4 \xrightarrow{\epsilon, Z_0/Z_0} q_{\text{acc}}\).

Так как на фазе заталкивания счёт удваивается (\(AA\) на каждый \(a\)), снятие одного \(A\) на каждый \(b\) в первой ветке даёт \(2n\) символов \(b\), а чередование «два \(b\) на один \(A\)» во второй ветке даёт \(n\) символов \(b\).

(c) \(L_3 = \{a^i b^j c^k d^l \mid (i = k \text{ or } j = l),\; i \geq 1,\; j \geq 1\}\).

Пишем \(L_3 = L_A \cup L_B\), где \(L_A = \{a^i b^j c^i d^l\}\) (считаем \(a\) с \(c\)) и \(L_B = \{a^i b^j c^k d^j\}\) (считаем \(b\) с \(d\)). Недетерминированно выбираем:

Ветка A (\(i = k\)): кладём \(A\) на каждый \(a\); читаем \(b\), не трогая стек; снимаем \(A\) на каждый \(c\); читаем \(d\) свободно; принимаем при опустошении стека.
Ветка B (\(j = l\)): читаем \(a\) свободно; кладём \(B\) на каждый \(b\); читаем \(c\) свободно; снимаем \(B\) на каждый \(d\); принимаем при опустошении стека.

Каждая ветка — стандартный DPDA; NPDA — их объединение через общее начальное состояние с двумя исходящими \(\epsilon\)-переходами.

4.2. Построение NTM для двух языков (Лаба 10, Задание 2)

Постройте NTM, распознающие следующие языки:

\(L_1 = \{ww \mid w \in \{a, b\}^+\}\) — строки, являющиеся конкатенацией непустого слова с самим собой.
\(L_2 = \{ww^R \mid w \in \{a, b\}^+\}\) — палиндромы чётной длины.

Показать решение

(a) \(L_1 = \{ww \mid w \in \{a,b\}^+\}\).

Строка должна иметь чётную длину \(2n\), а первая и вторая половины совпадают. Стандартный подход DTM использует несколько проходов, NTM может угадать середину.

Конструкция двухленточной NTM:

Недетерминированно угадать середину: NTM ставит метку в некоторой позиции входа (угадывая, где кончается первая половина и начинается вторая).
Скопировать первую половину на ленту 2.
Сравнить ленту 2 со второй половиной посимвольно.
Принять тогда и только тогда, когда сравнение успешно и половины одинаковой длины.

На ветке с верной догадкой NTM принимает; на остальных — отвергает. По экзистенциальному принятию NTM принимает \(ww\), если существует успешная ветка.

(b) \(L_2 = \{ww^R \mid w \in \{a,b\}^+\}\).

Аналогично (a), но вторая половина должна быть разворотом первой.

Конструкция двухленточной NTM:

Недетерминированно угадать середину.
Скопировать первую половину на ленту 2 в обратном порядке (справа налево на ленте 2).
Сравнить ленту 2 со второй половиной слева направо.
Принять при успешном сравнении.

В качестве альтернативы одноленточная NTM может: 1. Недетерминированно угадать середину и отметить её. 2. Сравнивать первый символ с последним, второй с предпоследним и т.д., перемещаясь туда-сюда и отмечая уже сопоставленные пары.

4.3. NPDA для языка-объединения (Лаба 10, Домашнее задание 1)

Постройте NPDA, распознающий язык: \[L_1 = \{a^n b^n \mid n \geq 0\} \cup \{a^{2n} \mid n \geq 0\}\]

Показать решение

Язык — объединение двух более простых:

\(L_A = \{a^n b^n \mid n \geq 0\}\): пустая строка плюс \(a^n b^n\) при \(n \geq 1\).
\(L_B = \{a^{2n} \mid n \geq 0\}\): строки из \(a\) чётной длины (включая \(\epsilon\)).

NPDA через объединение:

Вводим новое начальное состояние \(q_{\text{start}}\) с \(\epsilon\)-переходами в начальные состояния двух подавтоматов.

Подавтомат для \(L_A\) (стандартный DPDA для \(a^n b^n\)):

\(s_0\): кладём \(A\) на каждый \(a\). Переход в \(s_1\) на первом \(b\).
\(s_1\): снимаем \(A\) на каждый \(b\). Переход в принимающее \(s_2\), когда на стеке \(Z_0\).
\(s_2\) (принимающее): также принимаем \(\epsilon\) из \(s_0\) через переход \(\epsilon, Z_0/Z_0\).

Подавтомат для \(L_B\) (чётное число \(a\)):

\(t_0\) (принимающее): читаем \(a\), переходим в \(t_1\).
\(t_1\): читаем \(a\), возвращаемся в \(t_0\) (принимающее).
Операции со стеком: класть/снимать маркер на каждые два \(a\), либо просто считать чётность состоянием (стек кроме \(Z_0\) не нужен).

Принимающие состояния подавтомата \(L_B\): \(t_0\) (после чётного числа \(a\), включая ноль).

Полный NPDA:

\(q_{\text{start}} \xrightarrow{\epsilon, Z_0/Z_0} s_0\) и \(q_{\text{start}} \xrightarrow{\epsilon, Z_0/Z_0} t_0\).
Внутри каждый подавтомат работает как описано.

Принимаются и \(\epsilon\), и пустая строка (и \(s_0\) с пустым стеком, и \(t_0\) достижимы из \(q_{\text{start}}\) на \(\epsilon\)).

4.4. NTM для объединения языков со счётом (Лаба 10, Домашнее задание 2)

Постройте NTM, распознающую язык: \[L_2 = \{a^n b^n \mid n \geq 0\} \cup \{a^n b^{2n} \mid n \geq 0\}\]

Показать решение

Язык требует, чтобы NTM в начале недетерминированно выбрала, к какому подъязыку относится вход, затем проверяла детерминированно.

Недетерминированный выбор. В самом начале NTM ветвится на два пути вычисления:

Путь A: проверить \(a^n b^n\).
Путь B: проверить \(a^n b^{2n}\).

Проверка \(a^n b^n\) (путь A) на двухленточной MT:

Проходим ленту 1, считая число \(a\): отмечаем каждый \(a\) на ленте 1 и пишем засечку на ленту 2.
На каждый \(b\) стираем одну засечку на ленте 2.
Принимаем, если лента 2 пуста ровно в момент исчерпания всех \(b\).

Проверка \(a^n b^{2n}\) (путь B) на двухленточной MT:

Сканируем \(a\) и пишем две засечки на ленту 2 на каждый \(a\).
На каждый \(b\) стираем одну засечку на ленте 2.
Принимаем, если лента 2 пуста ровно при исчерпании всех \(b\).

Обе подпроцедуры реализуются как стандартные детерминированные шаги MT. NTM оборачивает их недетерминированным начальным ветвлением. Для объединения достаточно принятия на одном из путей.

4.5. DPDA для \(a^n b^n\) (Туториал 10, Пример 1)

Постройте DPDA для \(L_1 = \{a^n b^n \mid n \geq 1\}\) и проследите работу на строке \(aabb\).

Показать решение

Состояния: \(q_0\) (фаза заталкивания), \(q_1\) (фаза снятия), \(q_2\) (принимающее).

Функция переходов:

\(q_0, a, Z_0 \to q_0, AZ_0\) — первый \(A\) на \(Z_0\).
\(q_0, a, A \to q_0, AA\) — дополнительные \(A\).
\(q_0, b, A \to q_1, \epsilon\) — переход в фазу снятия на первом \(b\); снимаем \(A\).
\(q_1, b, A \to q_1, \epsilon\) — продолжаем снимать \(A\) на каждый \(b\).
\(q_1, \epsilon, Z_0 \to q_2, Z_0\) — стек вернулся к начальному символу; принимаем.

Трассировка на \(aabb\):

Шаг	Вход	Состояние	Стек (вершина слева)
0	\(aabb\)	\(q_0\)	\(Z_0\)
1	\(abb\)	\(q_0\)	\(AZ_0\)
2	\(bb\)	\(q_0\)	\(AAZ_0\)
3	\(b\)	\(q_1\)	\(AZ_0\)
4	\(\epsilon\)	\(q_1\)	\(Z_0\)
5	\(\epsilon\)	\(q_2\)	\(Z_0\)

DPDA достигает \(q_2\) (принимающее) с пустым остатком входа. ✓

4.6. NPDA для \(a^n b^n\) (Туториал 10, Пример 2)

Постройте NPDA для \(L_1 = \{a^n b^n \mid n \geq 1\}\), используя недетерминированный \(\epsilon\)-переход для смены фазы, и объясните, чем это отличается от варианта с DPDA.

Показать решение

Состояния: \(q_0\) (фаза заталкивания), \(q_1\) (фаза снятия), \(q_2\) (принимающее).

Функция переходов:

\(q_0, a, Z_0 \to q_0, AZ_0\) и \(q_0, a, A \to q_0, AA\) — кладём \(A\) на каждый \(a\).
Недетерминированный спонтанный ход: \(q_0, \epsilon, A \to q_1, A\) — недетерминированно «полагаем», что все \(a\) прочитаны, и переходим в фазу снятия (без чтения входа).
\(q_1, b, A \to q_1, \epsilon\) — снимаем \(A\) на каждый \(b\).
\(q_1, \epsilon, Z_0 \to q_2, Z_0\) — принимаем при стеке \(Z_0\).

Отличие от DPDA. У DPDA переход из фазы заталкивания в фазу снятия вызывается фактическим чтением первого \(b\). У этого NPDA переход происходит по \(\epsilon\)-переходу в любой момент фазы чтения \(a\). На большинстве веток догадка неверна и пути отвергаются; только ветка, где \(\epsilon\) срабатывает ровно после \(n\) символов \(a\), корректно входит в фазу снятия и принимает \(a^n b^n\).

Это каноническая иллюстрация того, как недетерминизм может «угадывать» структурные границы, которые детерминированная машина определяла бы по входу.

4.7. NPDA для палиндромов чётной длины (Туториал 10, Пример 3)

Постройте NPDA для \(L = \{vv^R \mid v \in \{a, b\}^*\}\) и объясните, почему этот язык не распознаётся ни одним DPDA.

Показать решение

Состояния: \(q_0\) (фаза заталкивания), \(q_1\) (фаза снятия / сопоставления), \(q_2\) (принимающее).

Переходы фазы заталкивания (\(q_0\), кладём символ на стек на каждый входной символ):

Вход	Вершина стека	Новая вершина	Смысл
\(a\)	\(Z_0\)	\(AZ_0\)	кладём \(A\)
\(a\)	\(A\)	\(AA\)	кладём \(A\)
\(a\)	\(B\)	\(AB\)	кладём \(A\)
\(b\)	\(Z_0\)	\(BZ_0\)	кладём \(B\)
\(b\)	\(A\)	\(BA\)	кладём \(B\)
\(b\)	\(B\)	\(BB\)	кладём \(B\)

Недетерминированные переходы середины (из \(q_0\) в \(q_1\), \(\epsilon\)-ходы):

\(\epsilon, Z_0 / Z_0\), \(\epsilon, A / A\), \(\epsilon, B / B\) — угадать середину в любой момент.

Фаза снятия (\(q_1\)):

\(a, A / \epsilon\) — входной \(a\) совпадает с \(A\) на стеке; снимаем.
\(b, B / \epsilon\) — входной \(b\) совпадает с \(B\); снимаем.

Принятие: \(q_1, \epsilon, Z_0 / Z_0 \to q_2\) — принять при стеке \(Z_0\) (все символы согласованы).

Почему не подходит DPDA. DPDA должен знать точный момент середины строки. Для \(abba\) середина — между двумя \(b\). Но для \(abba\) и \(abbaabba\) позиции середины разные, и без разделителя (как в \(vcv^R\)) детерминированная машина не может решить, когда прекращать заталкивание и начинать снятие. Недетерминированные \(\epsilon\)-переходы позволяют NPDA «угадывать» середину на каждой ветке; ровно одна верная ветка принимает.

4.8. Алгоритм Клини на двухсостоятельном автомате (Туториал 10, Пример 4)

Примените алгоритм Клини к DFSA с \(Q = \{q_0, q_1\}\): \(q_0\) — начальное и принимающее; у \(q_0\) петля на \(0\); переход \(q_0 \xrightarrow{1} q_1\); переход \(q_1 \xrightarrow{0} q_0\).

Вычислите \(R_{ij}^k\) для всех \((i, j)\) при \(k = -1\), \(k = 0\) и \(k = 1\) и выпишите итоговое регулярное выражение.

Показать решение

Шаг \(k = -1\) (только прямые переходы).

\(R_{00}^{-1} = 0 \mid \epsilon\) — петля на \(0\) плюс \(\epsilon\) (остаться в \(q_0\), ничего не читая).
\(R_{01}^{-1} = 1\) — ребро \(q_0 \to q_1\) по \(1\).
\(R_{10}^{-1} = 0\) — ребро \(q_1 \to q_0\) по \(0\).
\(R_{11}^{-1} = \epsilon\) — нет петли, только \(\epsilon\) (остаться в \(q_1\)).

Шаг \(k = 0\) (пути могут проходить через \(q_0\)).

Применяем \(R_{ij}^0 = R_{i0}^{-1}(R_{00}^{-1})^* R_{0j}^{-1} \mid R_{ij}^{-1}\):

\(R_{00}^0 = (0 \mid \epsilon)(0 \mid \epsilon)^*(0 \mid \epsilon) \mid (0 \mid \epsilon) = 0^*\)
\(R_{01}^0 = (0 \mid \epsilon)(0 \mid \epsilon)^* \cdot 1 \mid 1 = 0^* 1\)
\(R_{10}^0 = 0 \cdot (0 \mid \epsilon)^* \cdot (0 \mid \epsilon) \mid 0 = 00^*\)
\(R_{11}^0 = 0 \cdot (0 \mid \epsilon)^* \cdot 1 \mid \epsilon = 00^* 1 \mid \epsilon\)

Шаг \(k = 1\) (пути могут проходить через \(q_0\) и \(q_1\)).

Применяем \(R_{ij}^1 = R_{i1}^0 (R_{11}^0)^* R_{1j}^0 \mid R_{ij}^0\):

\(R_{00}^1 = R_{01}^0(R_{11}^0)^* R_{10}^0 \mid R_{00}^0\) \(= 0^*1 \cdot (00^*1 \mid \epsilon)^* \cdot 00^* \mid 0^*\) \(= 0^*1(00^*1)^* 00^* \mid 0^*\) \(= (0^*100^*)^*\)

Ответ. Множество принимающих состояний \(F = \{q_0\}\), поэтому ответ — \(R_{00}^1 = (0^*100^*)^*\).

Это язык всех строк над \(\{0, 1\}\), в которых каждая \(1\) сопровождается хотя бы одним \(0\) — эквивалентно: ни одна строка не оканчивается на \(1\) (каждая \(1\) лежит внутри блока \(0^*10^+\)).

4.9. Алгоритм Клини на трёхсостоятельном автомате (Туториал 10, Пример 5)

Примените алгоритм Клини к DFSA с \(Q = \{q_0, q_1, q_2\}\), принимающими \(F = \{q_1, q_2\}\) и переходами:

\(q_0 \xrightarrow{a} q_0\) (петля), \(q_0 \xrightarrow{b} q_1\)
\(q_1 \xrightarrow{b} q_1\) (петля), \(q_1 \xrightarrow{a} q_2\)
\(q_2 \xrightarrow{a} q_1\), \(q_2 \xrightarrow{b} q_1\)

Вычислите все значения \(R_{ij}^k\) до \(k = 2\) и выпишите итоговое регулярное выражение.

Показать решение

Шаг \(k = -1\).

\(R_{00}^{-1} = a \mid \epsilon\), \(R_{01}^{-1} = b\), \(R_{02}^{-1} = \emptyset\)
\(R_{10}^{-1} = \emptyset\), \(R_{11}^{-1} = b \mid \epsilon\), \(R_{12}^{-1} = a\)
\(R_{20}^{-1} = \emptyset\), \(R_{21}^{-1} = a \mid b\), \(R_{22}^{-1} = \epsilon\)

Шаг \(k = 0\) (разрешаем пути через \(q_0\)).

По формуле \(R_{ij}^0 = R_{i0}^{-1}(R_{00}^{-1})^* R_{0j}^{-1} \mid R_{ij}^{-1}\):

\(R_{00}^0 = (a \mid \epsilon)(a \mid \epsilon)^*(a \mid \epsilon) \mid (a \mid \epsilon) = a^*\)
\(R_{01}^0 = (a \mid \epsilon)(a \mid \epsilon)^* b \mid b = a^* b\)
\(R_{02}^0 = (a \mid \epsilon)(a \mid \epsilon)^* \emptyset \mid \emptyset = \emptyset\)
\(R_{10}^0 = \emptyset(a \mid \epsilon)^*(a \mid \epsilon) \mid \emptyset = \emptyset\)
\(R_{11}^0 = \emptyset(a \mid \epsilon)^* b \mid (b \mid \epsilon) = b \mid \epsilon\)
\(R_{12}^0 = \emptyset(a \mid \epsilon)^* \emptyset \mid a = a\)
\(R_{20}^0 = \emptyset\), \(R_{21}^0 = a \mid b\), \(R_{22}^0 = \epsilon\)

Шаг \(k = 1\) (разрешаем пути через \(q_0\) и \(q_1\)).

По формуле \(R_{ij}^1 = R_{i1}^0 (R_{11}^0)^* R_{1j}^0 \mid R_{ij}^0\):

\(R_{00}^1 = a^* b (b \mid \epsilon)^* \emptyset \mid a^* = a^*\)
\(R_{01}^1 = a^* b (b \mid \epsilon)^* (b \mid \epsilon) \mid a^* b = a^* b b^* = a^* bb^*\)
\(R_{02}^1 = a^* b (b \mid \epsilon)^* a \mid \emptyset = a^* bb^* a\)
\(R_{10}^1 = \emptyset\), \(R_{11}^1 = (b \mid \epsilon)(b \mid \epsilon)^*(b \mid \epsilon) \mid (b \mid \epsilon) = b^*\)
\(R_{12}^1 = (b \mid \epsilon)(b \mid \epsilon)^* a \mid a = b^* a\)
\(R_{20}^1 = \emptyset\)
\(R_{21}^1 = (a \mid b)(b \mid \epsilon)^*(b \mid \epsilon) \mid (a \mid b) = (a \mid b)b^*\)
\(R_{22}^1 = (a \mid b)(b \mid \epsilon)^* a \mid \epsilon = (a \mid b)b^* a \mid \epsilon\)

Шаг \(k = 2\) (разрешаем все пути через \(q_0\), \(q_1\), \(q_2\)).

Ключевое вычисление для ответа (принимающие — \(q_1\) и \(q_2\)):

\(R_{01}^2 = R_{02}^1(R_{22}^1)^* R_{21}^1 \mid R_{01}^1\)

\(= a^* bb^* a \cdot ((a \mid b)b^* a \mid \epsilon)^* \cdot (a \mid b)b^* \mid a^* bb^*\)

\(= a^* bb^* \bigl(a(a \mid b)b^*\bigr)^*\)

\(R_{02}^2 = R_{02}^1(R_{22}^1)^* R_{22}^1 \mid R_{02}^1\)

\(= a^* bb^* a \cdot ((a \mid b)b^*a \mid \epsilon)^* \cdot ((a \mid b)b^*a \mid \epsilon) \mid a^*bb^*a\)

\(= a^* bb^* \bigl(a(a \mid b)b^*\bigr)^* a\)

Итог. Так как \(F = \{q_1, q_2\}\):

\[R_{01}^2 \mid R_{02}^2 = a^* bb^*\bigl(a(a \mid b)b^*\bigr)^*(\epsilon \mid a)\]

Это язык строк, которые начинаются с любого числа \(a\), затем содержат хотя бы один \(b\), после чего идут блоки вида \((a(a \mid b)b^*)\), с опциональным завершающим \(a\).